我的技术点滴总结：一种加权随机抽奖算法 |
您所在的位置：网站首页 › 随机抽数 千千万的概率是多少啊视频 › 我的技术点滴总结：一种加权随机抽奖算法 |
我的技术点滴总结：一种加权随机抽奖算法
|
1.引言
一场活动少不了抽奖，抽奖的方式有很多： 循点私，可以在指定的用户范围内抽奖；只为走形式，可以直接让指定人中奖；如果要公平点，可以来个随机抽奖；……循私的事我们就不去宏扬了，还是介绍一种比较公平的抽奖算法，毕竟这种涉及到利益的事，公平才是最难的。 抽奖中有一个比较典型的问题：重复中奖。 抽奖往往不只一轮，在多轮抽奖下，如果之前中过奖的人接连继续中奖，这场活动会瞬间引来大家非议，主办方也会陷入尴尬，为避免把一场活动办砸，我们有必要解决下这个问题。 针对这个问题，从用户层面，一般有两种做法： 不能重复中奖：粗暴直接，将中过奖的人都排除掉；降低概率：允许重复中奖，但要降低已中奖人的再次中奖概率；第一种比较简单，我们今天主要讨论第二种。 2.思路要降低已中奖者的中奖概率，至少要满足两点诉求： 对于已中奖者，再次中奖概率要低于未中奖者；对于中奖次数多的用户，中奖概率要低于中奖次数少的用户；一个有效的办法是：按中奖次数给相应用户降低权重。 2.1 降权算法假设每个人初始权重值都是20， 现在有A、B、C、D、E共5个人，分别中过4、3、2、1、0次奖，我们可以让权重值按照每个人中过奖的次数按指数衰减，衰减后每个人的权重变化如下： A：20 >> 4 = 1 （用向右移4位来表示权重衰减4次，下面同理）B：20 >> 3 = 2C: 20 >> 2 = 5D: 20 >> 1 = 10E: 20 >> 0 = 20这里采用指数方式是为了让衰减效果更好，可以看出中奖次数越多，权重衰减得越明显。 如果用代码实现权重计算，示例并说明如下： winCount：表示用户列表+中奖次数数据，其中数组下标表示用户，数组元素表示用户的中奖次数；当权重衰减到小于1时，默认为1，以保证极端情况下每个用户仍然有中奖概率；return weights: 计算好的用户权重数据； func calculateWeights(winCount []int) []int { weights := make([]int, len(winCount)) for i, count := range winCount { weight := 20 >> count // 降权 if weight < 1 { weight = 1 } weights[i] = weight } return weights } 2.2 加权抽奖为了更好理解，我们先看下最简单的抽奖做法，在0到n（用户数量）之间取随机数，抽出的随机数就是中奖者，每个用户的中奖机会相同。 func draw() string { users := []string{"A", "B", "C", "D", "E"} rand.Seed(time.Now().UnixNano()) // 随机数种子 index := rand.Intn(len(users)) return users[index] }如果加入权重，每个用户的中奖机会则是不同的，比较直观的做法就是按照权重在用户列表中重复添加一定数量的用户，例如： E的权重是20，则用户列表中重复20个ED的权重是10，则用户列表中重复10个DC的权重是5，则用户列表中重复5个CB的权重是2，则用户列表中重复2个BA的权重是1，则用户列表中重复1个A（等于没有重复）最终加入权重后的用户列表如下： 基于这个用户列表作随机算法抽取，显然中奖概率是：E > D > C > B > A，这样就产生了加权的效果。 2.3 算法改进上面重复添加用户的作法虽然实现了效果，但是会有个问题：权重用户列表会随着权重值以几何倍数增长。原因如下： 上面示意的5个用户只是为了说明方便，实际场景可能会有成千上万的用户，甚至更多；当权重值很大时，权重用户列表可能会非常大；假设有10000用户，权重值1000，则用户列表需要从10000扩充到一千万；列表无限制增长，会给内存和程序的稳定性带来风险；基于此，我们还需要对算法作一些改进。 有一种做法是将权重值叠加，计算一个总权重数，在总权重范围内做随机数抽取，最终看随机数落在哪个用户的权重区间。还以上面的例子说明： A的权重是1，则A的权重区间是[0-0]B的权重是2，则B的权重区间是[1-2];C的权重是5，则B的权重区间是[3-7];D的权重是10，则B的权重区间是[8-17];E的权重是20，则B的权重区间是[18-37];A、B、C、D、E加起来的总权重是38，在38之内抽取随机数，其实有效抽取区间是[0-37]假设如果抽到的随机数是5，则落在C的权重区间，即C中奖。用代码表示的话大概如下： 入参userWeights数组表示用户列表及每个用户的权重，仍然用数组下标表示用户，数组元素值表示权重（这里假设已经计算好权重）;返回值win表示抽中的用户，即用户在userWeights中对应的下标； func draw(userWeights []int) (win int) { // 计算总权重 var totalWeight int for _, weight := range userWeights { totalWeight += weight } // 在总权重范围内随机抽取一个权重值 n rand.Seed(time.Now().UnixNano()) n := rand.Intn(totalWeight) // 遍历用户列表，将n与每个用户的权重做减法，当n第一次小于0时，就表示n落在这个用户的权重区间内，此用户中奖 for i, weight := range userWeights { n -= weight if n < 0 { win = i break } } return }通过此番改造后，算法性能只和用户列表大小有关，与默认权重不再有关系。 2.4 支持同时抽多个用户年会抽奖一轮往往不止抽一个用户，如果要抽取多个用户，上面的实现还需要稍微改造下。 首先入参需要扩展一个参数num, 表示一次抽取的用户数；开启一个循环，多次运行上面的抽奖算法；还需要处理一个问题：循环中的前后两次有可能抽中同一用户，处理方式如下： 如果抽到的用户之前已经被抽中过，则跳过此用户，相当于把中奖机会平移给后面未中奖的用户；总权重要减掉已经中过奖的用户，以保证下一次抽奖抽到的随机数n能落在有效用户身上。 func draw(userWeights []int, num int) []int { winned := make([]int, 0, num) …… // 总权重计算省略 // 多次抽取 for i := 0; i < num; i++ { n := this.random.Intn(totalWeight) for j, weight := range userWeights { if contains(winned, j) { // 已经中过奖的用户直接跳过，contains用于检查数组中是否包含一个元素，代码省略 continue } n -= weight if n < 0 { totalWeight -= weight // 总权重totoalWeight要减掉已经中奖的用户权重 winned = append(winned, j) break } } } return winned } 3. 提取工具库为方便使用，我们可以封装一个工具类，这个工具类定义如下： type WeightedRandom struct { random *rand.Rand // 随机数生成器 defaultWeight int // 用户初始权重 }它需要有一个构造方法来初始化随机数生成器，并支持调用方指定初始权重。 func NewWeightedRandom(defaultWeight int) *WeightedRandom { return &WeightedRandom{ random: rand.New(rand.NewSource(time.Now().UnixNano())), defaultWeight: defaultWeight, } }它还需要有一个公开的API方法提供抽奖功能，这个方法只需要做两件事，直接调用我们之前封装好的两个方法就行： 根据已中奖次数计算权重；根据权重来抽取一定数量的用户； func (this *WeightedRandom) Draw(winCount []int, num int) []int { userWeights := this.calculateWeights(winCount) return this.draw(userWeights, num) }关于初始权重defaultWeight，稍微说明下，这个参数决定了中奖次数对权重影响的细腻程度； 值越大，权重体现的越丰富，特别是对于用户中奖次数层次不齐的场景；但也没必要太大，建议根据实际场景中用户可能会有的中奖次数区间来设；这篇文章到这里就基本介绍完了，虽然我们是拿抽奖这个业务来展开的设计过程，但其实这个算法也可以用在其它场景，例如：流量分配。推荐大家在工作中实际应用，方能理解的更深刻。 代码参考：https://github.com/golfxiao/gotool |
![[权重对抽取结果影响的示意图]](https://img-blog.csdnimg.cn/12546fc64a1f4986997b74b3924a5c19.png)
【本文地址】
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |